package com.gitee.wsl.transform.encode.pinyin.interval


class IntervalTree(intervals: List<Intervalable>) {
    private val rootNode: IntervalNode = IntervalNode(intervals)

    fun removeOverlaps(intervalsRead: List<Intervalable>): List<Intervalable> {
        // Sort the intervals on size, then left-most position
        val intervals = intervalsRead.toMutableList()

        //sort(intervals, IntervalableComparatorBySize)
        intervals.sortWith(IntervalableComparatorBySize)

        val removeIntervals = mutableSetOf<Intervalable>()

        for (interval in intervals) {
            // If the interval was already removed, ignore it
            if (removeIntervals.contains(interval)) {
                continue
            }

            // Remove all overallping intervals
            removeIntervals.addAll(findOverlaps(interval))
        }

        // Remove all intervals that were overlapping
        for (removeInterval in removeIntervals) {
            intervals.remove(removeInterval)
        }

        // Sort the intervals, now on left-most position only
        //sort(intervals, IntervalableComparatorByPosition)
        intervals.sortWith(IntervalableComparatorByPosition)

        return intervals
    }

    fun findOverlaps(interval: Intervalable): List<Intervalable> {
        return rootNode.findOverlaps(interval)
    }
}
